/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.vijos;

import javax.management.relation.RoleUnresolved;
import java.util.Arrays;

/**
 * @author : sunzb(sunzb@hsit.com.cn)
 * @date: 2019/4/18
 */
//均分纸牌
public class P4_3_1123 {

    public static int test(int[] input) {
        int num = dataVerify(input);
        Arrays.sort(input);
        int indexLeft = 0;
        int indexRight = input.length - 1;
        int move = 0;
        while (indexLeft < indexRight) {
            int deltaLeft = num - input[indexLeft];
            int deltaRight = input[indexRight] - num;
            if (deltaRight > deltaLeft) {
                input[indexLeft] = num;
                input[indexRight] -= deltaLeft;
                indexLeft++;
                move++;
            } else if (deltaRight == deltaLeft) {
                input[indexLeft] = num;
                input[indexRight] = num;
                indexLeft++;
                indexRight--;
                if (deltaLeft != 0) {
                    move++;
                }
            } else {
                input[indexLeft] += deltaRight;
                input[indexRight] = num;
                indexRight--;
                move++;
            }
        }
        return move;
    }

    private static int dataVerify(int[] input) {
        int sum = 0;
        for (int i = 0; i < input.length; i++) {
            sum += input[i];
        }
        if (sum % input.length != 0) {
            throw new RuntimeException(
                    String.format("纸牌总数%s不是%s（堆数）的倍数", sum, input.length));
        }
        return sum / input.length;
    }

    public static void main(String[] args) {
        System.out.println(test(new int[] {9, 8, 17, 6}));
    }
}
